{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Extract Kth Character From The Rope Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: getKthCharacter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #从 Rope 树中提取第 K 个字符"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个二叉树的根节点 <code>root</code> 和整数 <code>k</code>。除了左右孩子之外，该树的每个节点还有另外两个属性：一个仅包含小写英文字母（可能为空）的 <strong>字符串</strong> <code>node.val</code> 和一个非负整数 <code>node.len</code>。这棵树中有两种类型的节点：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><strong>叶子节点</strong>：这些节点没有子节点，<code>node.len = 0</code>，<code>node.val</code> 是一个 <strong>非空</strong> 字符串。</li>\n",
    "\t<li><strong>内部节点</strong>：这些节点至少有一个子节点（最多两个子节点），<code>node.len &gt; 0</code>，<code>node.val</code> 是一个 <strong>空</strong> 字符串。</li>\n",
    "</ul>\n",
    "\n",
    "<p>上述描述的树被称为 Rope 二叉树。现在我们用以下递归方式定义 <code>S[node]</code>：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果 <code>node</code> 是一个叶子节点，则 <code>S[node] = node.val</code>，</li>\n",
    "\t<li>否则，如果 <code>node</code> 是一个内部节点，则 <code>S[node] = concat(S[node.left], S[node.right])</code>，且 <code>S[node].length = node.len</code>。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回字符串 <code>S[root]</code> 的第 <code>k</code> 个字符。</p>\n",
    "\n",
    "<p><strong>注意</strong>：如果 <code>s</code> 和 <code>p</code> 是两个字符串，则 <code>concat(s, p)</code> 是将字符串 <code>p</code> 连接到 <code>s</code> 后面的字符串。例如，<code>concat(\"ab\", \"zz\") = \"abzz\"</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>root = [10,4,\"abcpoe\",\"g\",\"rta\"], k = 6\n",
    "<b>输出：</b>\"b\"\n",
    "<b>解释：</b>在下面的图片中，我们在内部节点上放置一个表示 <code>node.len</code> 的整数，在叶子节点上放置一个表示 <code>node.val</code> 的字符串。 你可以看到，<code>S[root] = concat(concat(\"g\", \"rta\"), \"abcpoe\") = \"grtaabcpoe\"</code>。因此，<code>S[root][5]</code>，表示它的第6个字符，等于 \"b\"。\n",
    "</pre>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/05/14/example1.png\" style=\"width: 300px; height: 213px; margin-left: 280px; margin-right: 280px;\" /></p>\n",
    "\n",
    "<p><strong class=\"example\">示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>root = [12,6,6,\"abc\",\"efg\",\"hij\",\"klm\"], k = 3\n",
    "<b>输出：</b>\"c\"\n",
    "<b>解释：</b>在下面的图片中，我们在内部节点上放置一个表示 <code>node.len</code> 的整数，在叶子节点上放置一个表示 <code>node.val</code> 的字符串。 你可以看到，<code>S[root] = concat(concat(\"abc\", \"efg\"), concat(\"hij\", \"klm\")) = \"abcefghijklm\"</code>。因此，<code>S[root][2]</code>，表示它的第3个字符，等于 \"c\"。\n",
    "</pre>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/05/14/example2.png\" style=\"width: 400px; height: 232px; margin-left: 255px; margin-right: 255px;\" /></p>\n",
    "\n",
    "<p><strong class=\"example\">示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>root = [\"ropetree\"], k = 8\n",
    "<b>输出：</b>\"e\"\n",
    "<b>解释：</b>在下面的图片中，我们在内部节点上放置一个表示 <code>node.len</code> 的整数，在叶子节点上放置一个表示 <code>node.val</code> 的字符串。 你可以看到，<code>S[root] = \"ropetree\"</code>。因此，<code>S[root][7]</code>，表示它的第8个字符，等于 \"e\"。\n",
    "</pre>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/05/14/example3.png\" style=\"width: 80px; height: 78px; margin-left: 400px; margin-right: 400px;\" /></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>这棵树的节点数量在区间&nbsp;<code>[1, 10<sup>3</sup>]</code></li>\n",
    "\t<li><code>node.val</code> 仅包含小写英文字母</li>\n",
    "\t<li><code>0 &lt;= node.val.length &lt;= 50</code></li>\n",
    "\t<li><code>0 &lt;= node.len &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li>对于叶子节点， <code>node.len = 0</code> 且&nbsp;<code>node.val</code> 是非空的</li>\n",
    "\t<li>对于内部节点， <code>node.len &gt; 0 </code>&nbsp;且&nbsp;<code>node.val</code> 为空</li>\n",
    "\t<li><code>1 &lt;= k &lt;= S[root].length</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [extract-kth-character-from-the-rope-tree](https://leetcode.cn/problems/extract-kth-character-from-the-rope-tree/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [extract-kth-character-from-the-rope-tree](https://leetcode.cn/problems/extract-kth-character-from-the-rope-tree/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[10,4,\"abcpoe\",\"g\",\"rta\"]\\n6', '[12,6,6,\"abc\",\"efg\",\"hij\",\"klm\"]\\n3', '[\"ropetree\"]\\n8']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a rope tree node.\n",
    "# class RopeTreeNode(object):\n",
    "#     def __init__(self, len=0, val=\"\", left=None, right=None):\n",
    "#         self.len = len\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getKthCharacter(self, root: Optional[object], k: int) -> str:\n",
    "        \"\"\"\n",
    "        :type root: Optional[RopeTreeNode]\n",
    "        \"\"\"\n",
    "        def iterate(node):\n",
    "            if node:\n",
    "                if node.len:\n",
    "                    yield from iterate(node.left)\n",
    "                    yield from iterate(node.right)\n",
    "                else:\n",
    "                    yield node.val\n",
    "        for s in iterate(root):\n",
    "            n = len(s)\n",
    "            if k <= n:\n",
    "                return s[k-1]\n",
    "            k -= n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a rope tree node.\n",
    "# class RopeTreeNode(object):\n",
    "#     def __init__(self, len=0, val=\"\", left=None, right=None):\n",
    "#         self.len = len\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getKthCharacter(self, root: Optional[object], k: int) -> str:\n",
    "        ans=0\n",
    "        def dfs(node):\n",
    "            nonlocal k,ans\n",
    "            if node:\n",
    "                if node.len==0:\n",
    "                    if k==0: return\n",
    "                    elif len(node.val)>=k:\n",
    "                        ans=node.val[k-1]\n",
    "                        k=0\n",
    "                        return\n",
    "                    else: k-=len(node.val)\n",
    "                dfs(node.left)\n",
    "                dfs(node.right)\n",
    "        dfs(root)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a rope tree node.\n",
    "# class RopeTreeNode(object):\n",
    "#     def __init__(self, len=0, val=\"\", left=None, right=None):\n",
    "#         self.len = len\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getKthCharacter(self, root: Optional[object], k: int) -> str:\n",
    "        \"\"\"\n",
    "        :type root: Optional[RopeTreeNode]\n",
    "        \"\"\"\n",
    "        def get(node, x):\n",
    "            if node.val:\n",
    "                return node.val[x]\n",
    "            else:\n",
    "                y = 0\n",
    "                if node.left:\n",
    "                    a, b = node.left.val, node.left.len\n",
    "                    if a:\n",
    "                        y = len(a)\n",
    "                        if x < y: return a[x]\n",
    "                    else:\n",
    "                        if x < b: return get(node.left, x)\n",
    "                        y = b\n",
    "                x -= y\n",
    "                return get(node.right, x)\n",
    "        return get(root, k-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a rope tree node.\n",
    "# class RopeTreeNode(object):\n",
    "#     def __init__(self, len=0, val=\"\", left=None, right=None):\n",
    "#         self.len = len\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getKthCharacter(self, root: Optional[object], k: int) -> str:\n",
    "        \"\"\"\n",
    "        :type root: Optional[RopeTreeNode]\n",
    "        \"\"\"\n",
    "        self.res = ''\n",
    "        def dfs(node):\n",
    "            if not node:\n",
    "                return ''\n",
    "            if not node.left and not node.right:\n",
    "                self.res += node.val\n",
    "            dfs(node.left)\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        return self.res[k - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a rope tree node.\n",
    "# class RopeTreeNode(object):\n",
    "#     def __init__(self, len=0, val=\"\", left=None, right=None):\n",
    "#         self.len = len\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getKthCharacter(self, root: Optional[object], k: int) -> str:\n",
    "        \"\"\"\n",
    "        :type root: Optional[RopeTreeNode]\n",
    "        \"\"\"\n",
    "        ans = None \n",
    "        def dfs(node, cnt):\n",
    "            if not node or cnt==k: return cnt \n",
    "            if node.len==0:\n",
    "                for c in node.val:\n",
    "                    cnt += 1 \n",
    "                    if cnt==k:\n",
    "                        nonlocal ans \n",
    "                        ans = c \n",
    "            elif cnt+node.len<k: \n",
    "                cnt += node.len \n",
    "            else:\n",
    "                cnt = dfs(node.left, cnt)\n",
    "                cnt = dfs(node.right, cnt)\n",
    "            return cnt \n",
    "        cnt = dfs(root, 0)\n",
    "        return ans\n",
    "\n",
    "    # 递归\n",
    "    def getKthCharacter2(self, root: Optional[object], k: int) -> str:\n",
    "        if root.len==0:\n",
    "            return root.val[k-1]\n",
    "        if root.left:\n",
    "            if root.left.len==0:#字符串了 \n",
    "                g=len(root.left.val) \n",
    "                return root.left.val[k-1] if g>=k else self.getKthCharacter2(root.right,k-g)\n",
    "            else:#不是字符串 \n",
    "                if root.left.len>=k:\n",
    "                    return self.getKthCharacter2(root.left,k)\n",
    "                else:\n",
    "                    return self.getKthCharacter2(root.right,k-root.left.len)\n",
    "        return self.getKthCharacter2(root.right,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a rope tree node.\n",
    "# class RopeTreeNode(object):\n",
    "#     def __init__(self, len=0, val=\"\", left=None, right=None):\n",
    "#         self.len = len\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getKthCharacter(self, root: Optional[object], k: int) -> str:\n",
    "        \"\"\"\n",
    "        :type root: Optional[RopeTreeNode]\n",
    "        \"\"\"\n",
    "        # 数字节点都为内部节点，负责连接左右节点的字符串，返回最后root节点上的字符串的第k位字符\n",
    "        def dfs(node):\n",
    "            if node is None:\n",
    "                return ''\n",
    "            if node.left is None and node.right is None:\n",
    "                return node.val              \n",
    "            return dfs(node.left) + dfs(node.right)\n",
    "        return dfs(root)[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a rope tree node.\n",
    "# class RopeTreeNode(object):\n",
    "#     def __init__(self, len=0, val=\"\", left=None, right=None):\n",
    "#         self.len = len\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getKthCharacter(self, root: Optional[object], k: int) -> str:\n",
    "        \"\"\"\n",
    "        :type root: Optional[RopeTreeNode]\n",
    "        \"\"\"\n",
    "        self.ans = ''\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            #print(root.val if root.len == 0 else root.len)\n",
    "            self.ans += f'{root.val}'\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        #print(self.ans)\n",
    "        return self.ans[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a rope tree node.\n",
    "# class RopeTreeNode(object):\n",
    "#     def __init__(self, len=0, val=\"\", left=None, right=None):\n",
    "#         self.len = len\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getKthCharacter(self, root: Optional[object], k: int) -> str:\n",
    "        \"\"\"\n",
    "        :type root: Optional[RopeTreeNode]\n",
    "        \"\"\"\n",
    "        if root.val:\n",
    "            return root.val[k-1]\n",
    "\n",
    "        l = (len(root.left.val) if root.left.val else root.left.len) if root.left else 0\n",
    "        if l >= k:\n",
    "            return self.getKthCharacter(root.left, k)\n",
    "        return self.getKthCharacter(root.right, k - l)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a rope tree node.\n",
    "# class RopeTreeNode(object):\n",
    "#     def __init__(self, len=0, val=\"\", left=None, right=None):\n",
    "#         self.len = len\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getKthCharacter(self, root: Optional[object], k: int) -> str:\n",
    "        ans=[]\n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                if node.len==0:\n",
    "                    ans.append(node.val)\n",
    "                    return\n",
    "                dfs(node.left)\n",
    "                dfs(node.right)\n",
    "        dfs(root)\n",
    "        return \"\".join(ans)[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a rope tree node.\n",
    "# class RopeTreeNode(object):\n",
    "#     def __init__(self, len=0, val=\"\", left=None, right=None):\n",
    "#         self.len = len\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "# #         self.right = right\n",
    "# class Solution:\n",
    "#     def getKthCharacter(self, root: Optional[object], k: int) -> str:\n",
    "#         \"\"\"\n",
    "#         :type root: Optional[RopeTreeNode]\n",
    "#         \"\"\"\n",
    "#         def dfs(root):\n",
    "#             if not root:\n",
    "#                 return \"\"\n",
    "#             ret=root.val\n",
    "#             if root.left:\n",
    "#                 ret+=dfs(root.left)\n",
    "#             if root.right:\n",
    "#                 ret+=dfs(root.right)\n",
    "#             return ret \n",
    "\n",
    "#         ret=dfs(root)\n",
    "#         return ret[k-1]\n",
    "\n",
    " ### 网：梵           \n",
    "class Solution:\n",
    "\n",
    "    def getKthCharacter(self, root: Optional[object], k: int) -> str:\n",
    "\n",
    "        \"\"\"\n",
    "\n",
    "        :type root: Optional[RopeTreeNode]\n",
    "\n",
    "        \"\"\"\n",
    "\n",
    "        def DFS(root):\n",
    "\n",
    "            if not root:\n",
    "\n",
    "                return ''\n",
    "\n",
    "            if not root.left and not root.right:\n",
    "\n",
    "                return root.val\n",
    "\n",
    "            return DFS(root.left) + DFS(root.right)\n",
    "\n",
    "        return DFS(root)[k-1]\n",
    "\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a rope tree node.\n",
    "# class RopeTreeNode(object):\n",
    "#     def __init__(self, len=0, val=\"\", left=None, right=None):\n",
    "#         self.len = len\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getKthCharacter(self, root: Optional[object], k: int) -> str:\n",
    "        \"\"\"\n",
    "        :type root: Optional[RopeTreeNode]\n",
    "        \"\"\"\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return \"\"\n",
    "            ret=root.val\n",
    "            if root.left:\n",
    "                ret+=dfs(root.left)\n",
    "            if root.right:\n",
    "                ret+=dfs(root.right)\n",
    "            return ret \n",
    "\n",
    "        ret=dfs(root)\n",
    "        return ret[k-1]\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a rope tree node.\n",
    "# class RopeTreeNode(object):\n",
    "#     def __init__(self, len=0, val=\"\", left=None, right=None):\n",
    "#         self.len = len\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getKthCharacter(self, root: Optional[object], k: int) -> str:\n",
    "        ans=[]\n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                if node.len==0:\n",
    "                    ans.append(node.val)\n",
    "                    return\n",
    "                dfs(node.left)\n",
    "                dfs(node.right)\n",
    "        dfs(root)\n",
    "        return \"\".join(ans)[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a rope tree node.\n",
    "# class RopeTreeNode(object):\n",
    "#     def __init__(self, len=0, val=\"\", left=None, right=None):\n",
    "#         self.len = len\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getKthCharacter(self, root: Optional[object], k: int) -> str:\n",
    "        \"\"\"\n",
    "        :type root: Optional[RopeTreeNode]\n",
    "        \"\"\"\n",
    "        def dfs(node):\n",
    "          if not node:\n",
    "            return \"\"\n",
    "\n",
    "          if node.val:\n",
    "            return node.val\n",
    "\n",
    "          return dfs(node.left) + dfs(node.right)\n",
    "\n",
    "        return dfs(root)[k - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a rope tree node.\n",
    "# class RopeTreeNode(object):\n",
    "#     def __init__(self, len=0, val=\"\", left=None, right=None):\n",
    "#         self.len = len\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getKthCharacter(self, root: Optional[object], k: int) -> str:\n",
    "        \"\"\"\n",
    "        :type root: Optional[RopeTreeNode]\n",
    "        \"\"\"\n",
    "        def DFS(root):\n",
    "            if not root:\n",
    "                return ''\n",
    "            if not root.left and not root.right:\n",
    "                return root.val\n",
    "            return DFS(root.left) + DFS(root.right)\n",
    "        return DFS(root)[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def getKthCharacter(self, root: Optional[object], k: int) -> str:\n",
    "        if root.len==0:\n",
    "            return root.val[k-1]\n",
    "        if root.left:\n",
    "            if root.left.len==0:#字符串了 \n",
    "                g=len(root.left.val) \n",
    "                return root.left.val[k-1] if g>=k else self.getKthCharacter(root.right,k-g)\n",
    "            else:#不是字符串 \n",
    "                if root.left.len>=k:\n",
    "                    return self.getKthCharacter(root.left,k)\n",
    "                else:\n",
    "                    return self.getKthCharacter(root.right,k-root.left.len)\n",
    "        return self.getKthCharacter(root.right,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a rope tree node.\n",
    "# class RopeTreeNode(object):\n",
    "#     def __init__(self, len=0, val=\"\", left=None, right=None):\n",
    "#         self.len = len\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getKthCharacter(self, root: Optional[object], k: int) -> str:\n",
    "        \"\"\"\n",
    "        :type root: Optional[RopeTreeNode]\n",
    "        \"\"\"\n",
    "        res = ''\n",
    "        def dfs(node: Optional[object]):\n",
    "            nonlocal res\n",
    "            if not node:\n",
    "                return\n",
    "            dfs(node.left)\n",
    "            if node.len == 0:\n",
    "                res = res + node.val\n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        return res[k - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a rope tree node.\n",
    "# class RopeTreeNode(object):\n",
    "#     def __init__(self, len=0, val=\"\", left=None, right=None):\n",
    "#         self.len = len\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getKthCharacter(self, root: Optional[object], k: int) -> str:\n",
    "        \"\"\"\n",
    "        :type root: Optional[RopeTreeNode]\n",
    "        \"\"\"\n",
    "        def DFS(root):\n",
    "            if not root:\n",
    "                return ''\n",
    "            if not root.left and not root.right:\n",
    "                return root.val\n",
    "            return DFS(root.left) + DFS(root.right)\n",
    "        return DFS(root)[k-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a rope tree node.\n",
    "# class RopeTreeNode(object):\n",
    "#     def __init__(self, len=0, val=\"\", left=None, right=None):\n",
    "#         self.len = len\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def getKthCharacter(self, root: Optional[object], k: int) -> str:\n",
    "        ans=[]\n",
    "        def dfs(node):\n",
    "            if node:\n",
    "                if node.len==0:\n",
    "                    ans.append(node.val)\n",
    "                    return\n",
    "                dfs(node.left)\n",
    "                dfs(node.right)\n",
    "        dfs(root)\n",
    "        return \"\".join(ans)[k-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
